Elliptic curve cryptography (ECC) is based on the intractability of the discrete logarithm problem within a group over a finite field where the elements of the group are points on an elliptic curve. Cryptographic values generated using ECC schemes, such as the Elliptic Curve Digital Signature Algorithm (ECDSA), may be smaller than those generated using finite-field cryptography schemes, such as the Digital Signature Algorithm (DSA) and integer factorization cryptography schemes, such as the Rivest Shamir Adleman (RSA) algorithm, while still offering the same level of security. Smaller-sized cryptographic values are desirable because they may reduce storage and transmission requirements. ECDSA is described, for example, in “American National Standard for Financial Services ANS X9.62-2005: Public Key Cryptography for the Financial Services Industry—The Elliptic Curve Digital Signature Algorithm (ECDSA)”, Accredited Standards Committee X9, Inc., 2005. DSA and RSA are described, for example, in “Federal Information Processing Standards Publication 186-3 Digital Signature Standard (DSS)”, National Institute of Standards and Technology, June 2009.
A digital certificate may be used to bind a public key to its legitimate owner so that a recipient of the certificate can be confident as to the authenticity of the public key. Upon receiving a request from a requestor, a trusted third party, such as a certificate authority (CA), may provide a signed certificate to the requestor who may then send the certificate to a recipient. Alternatively, the recipient may be able to obtain the signed certificate directly from the CA. In a conventional or ‘explicit’ certificate scheme, the signature portion of the certificate is explicitly verified by the recipient in order to confirm that the public key contained in the certificate belongs to the purported owner (i.e., the requestor of the certificate). Subsequent communication between the requestor and the recipient is authenticated separately using, for example, a key agreement scheme or a digital signature scheme.
In an implicit certificate scheme, such as the Elliptic Curve Qu-Vanstone (ECQV) scheme, the implicit certificate does not explicitly contain the public key of the requestor, but instead contains data that may be used to reconstruct the public key, also known as public-key reconstruction data. Because the public key is not explicitly contained in the implicit certificate, the authenticity of the reconstructed public key can only be established after it is subsequently used in a successful run of some protocol, such as a key agreement scheme or a digital signature scheme.
Implicit certificates are generally smaller than explicit certificates and have fewer operational costs because some calculations that are typically performed independently in an explicit certificate scheme can be combined in an implicit certificate scheme. In addition to containing public-key reconstruction data, an implicit certificate also contains separate additional information. This additional information contributes to the size of the implicit certificate.